/**
 * @param {number[]} stones
 * @return {boolean}
 */
//  var canCross = function(stones) {
//     if(stones[1]!=1){
//         return false;
//     }
//     let map=new Array(stones[stones.length-1]+1).fill(0);
//     stones.forEach((e) => {
//         map[e]=1;
//     })
//     let n=map.length-1;
//     function dfs(index,k){
//         if(!map[index]||!k){
//             return false;
//         }
//         if(index==n){
//             return true;
//         }
//         return dfs(index+k-1,k-1) || dfs(index+k,k) || dfs(index+k+1,k+1);
//     }
//     return dfs(1,1);
// };

//无意义的DFS

var canCross = function(stones) {
    if(stones[1]!=1) return false;
    let n=stones.length;
    let map=new Map(Array.from(stones.entries()).map(([k,v]) => [v,k]));
    let dp=new Array(n).fill(0).map(() => new Set());
    dp[1].add(1);
    for(let i=1;i<n;i++){
        if(dp[i].size>0){
            for(let v of dp[i].values()){
                if(v-1>0&&map.has(stones[i]+v-1)){
                    dp[map.get(stones[i]+v-1)].add(v-1);
                }
                if(map.has(stones[i]+v)){
                    dp[map.get(stones[i]+v)].add(v);
                }
                if(map.has(stones[i]+v+1)){
                    dp[map.get(stones[i]+v+1)].add(v+1);
                }
            }
            if(dp[n-1].size>0){
                return true;
            }
        }
    }
    return false;
};
console.log(canCross(new Array(2000).fill(0).map((e,index) => index)))
// 执行用时：
// 148 ms
// , 在所有 JavaScript 提交中击败了
// 53.75%
// 的用户
// 内存消耗：
// 44.1 MB
// , 在所有 JavaScript 提交中击败了
// 66.25%
// 的用户